//
// Created by Senhai Xu on 2025/3/7.
//
//BM6 判断链表中是否有环
#include <unordered_set>
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};
 /**/
class Solution {
public:
  bool hasCycle(ListNode *head) {
      if (!head || !head->next) return false;
//      双指针 快慢指针
      ListNode *fast = head;
      ListNode *slow = head;
//     无环快指针会先为空，有环快慢指针会相遇
      while(fast!=nullptr && fast->next!=nullptr){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) return true;
      }
      return false;
      
  }
  bool hasCycle2(ListNode *head) {
      if (!head || !head->next) return false;
// 哈希表存储出现过的节点
      std::unordered_set<ListNode*> set;
      while(head){
        if(set.find(head->next)!=set.end()){
          return true;
        }
        else{
          set.insert(head);
          head = head->next;
        }
      }
      return false;
      
      
  }
};